package com.lcy.algorithm.huawei;

import java.util.HashMap;
import java.util.Map;

/**
 * 给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：
 * 每个元音字母，即 'a'，'e'，'i'，'o'，'u' ，在子字符串中都恰好出现了偶数次。
 *
 * 示例 1：
 *
 * 输入：s = "eleetminicoworoep"
 * 输出：13
 * 解释：最长子字符串是 "leetminicowor" ，它包含 e，i，o 各 2 个，以及 0 个 a，u 。
 * 示例 2：
 *
 * 输入：s = "leetcodeisgreat"
 * 输出：5
 * 解释：最长子字符串是 "leetc" ，其中包含 2 个 e 。
 * 示例 3：
 *
 * 输入：s = "bcbcbc"
 * 输出：6
 * 解释：这个示例中，字符串 "bcbcbc" 本身就是最长的，因为所有的元音 a，e，i，o，u 都出现了 0 次。
 */
public class 每个元音包含偶数次的最长子字符串 {
    public static void main(String[] args) {
        String s = "eleetminicoworoep"; // 示例输入
        int result = findTheLongestSubstring(s);
        System.out.println(result); // 输出结果为13

        String s2 = "leetcodeisgreat"; // 示例输入
        int result2 = findTheLongestSubstring(s2);
        System.out.println(result2); // 输出结果为5

        String s3 = "bcbcbc"; // 示例输入
        int result3 = findTheLongestSubstring(s3);
        System.out.println(result3); // 输出结果为6
    }

//    private static final String VOWELS = "aeiou";

    public static int findTheLongestSubstring(String s) {
        // aeiou每个元音用一个bit一共5个bit，32种奇偶次数组合状态，比如10101可以表示aiu出现奇数次数
        // oe则出现偶数次数，每当遍历一个字符，就可以改变当前的aeiou出现的奇偶次数，也即是改变状态
        // 显然，如果两次出现了同样的状态，假设第一次出现在i处
        // 第二次出现在j处，那么i+1-j之间的字符串肯定是满足aeiou出现均为偶数次数的
        // 因为只有经历了偶数个aeiou，才能回到之前的状态，为了使得合理的字符串最长
        // 那么第一次出现此状态时，就需要记录到下标，然后下次遇到相同状态，计算最大长度
        HashMap<Character,Integer> hashMap = new HashMap<Character, Integer>();
        HashMap<Integer,Integer> stateMap = new HashMap<Integer, Integer>();
        hashMap.put('a',1);
        hashMap.put('i',2);
        hashMap.put('u',4);
        hashMap.put('e',8);
        hashMap.put('o',16);
        int res = 0;
        int max = 0;
        stateMap.putIfAbsent(0, -1);
        for(int i = 0;i<s.length();i++){
            if (hashMap.containsKey(s.charAt(i))) {
                res ^= hashMap.get(s.charAt(i));
            }
            if (stateMap.containsKey(res)){
                max = Math.max(max,i-stateMap.get(res));
            }
            stateMap.putIfAbsent(res,i);
        }
        return max;
    }
}
